The Internet has revolutionized the movement of information. Routers or switches are typically used to direct traffic through networks or network segments. A principal function of a router or a switch is to move information, usually in the form of data packets, particularly Internet Protocol (IP) packets, from one network or network segment to another. Another function of a router or switch is to control the rate of flow of the information.
Receiving data packets, holding them in a queue (e.g., in an inbound buffer), and sending them out when a receiving buffer (e.g., an outbound buffer) is capable of accommodating such packets, is one method of managing the flow of information. A sending function will make a resource request (e.g., a buffer request), seeking an allocation of space in the outbound buffer for a data packet. A receiving function will respond to the buffer request. The response (e.g., a buffer reply), in general, will either indicate that the outbound buffer is able to receive the data packet, or will indicate that the outbound buffer cannot receive the data packet at this time, but may be able to at some later time. Other types of responses may be made, but these other types of responses are not necessarily relevant to the current discussion. Depending on the form of the buffer reply, the sending function either transfers the packet to the outbound memory or sends another buffer request at a later time.
For reasons known in the art, it is important to ensure that data packets are forwarded in a particular order, typically the order in which they are received. For example, many types of multi-part messages, such as streamed media data, may be degraded if their original packet order is not maintained. Thus, forwarding data packets in order is considered a key attribute for switches and routers.
Prior Art FIG. 1 illustrates data packets 1, 2, 3, 4, . . . , N queued in an inbound buffer 10 under control of some type of sending function (e.g., packet processor 20). Here, the data packets are stored according to the order in which they are to be forwarded; thus, data packet 1 should be forwarded before data packet 2, and so on.
According to the prior art, for data packet 1, packet processor 20 issues a buffer request to a receiving function that controls an outbound buffer (note that the receiving function can be performed by packet processor 20, or by another packet processor coupled to packet processor 20 by the network fabric). Generally speaking, if and when the outbound buffer is ready to receive data packet 1, the receiving function will respond with a buffer reply. After data packet 1 is sent, the process is repeated for data packet 2, and so on.
The prior art approach has the desired effect of ensuring that data packets are forwarded in the proper order, but at a loss of speed and efficiency. That is, while data packet 2 cannot be sent until after data packet 1 is sent, processing of data packet 2 is delayed until the processing of data packet 1 is completed.
Thus, the prior art is problematic because, even though data packet 2 may be ready to be sent, or even though an outbound buffer is ready to receive data packet 2, the data packet cannot be processed until data packet 1 is sent. This has the effect of reducing the rate at which data packets can be processed and decreasing the bandwidth of the router or switch. Accordingly, what is needed is a method and/or system that can increase data packet throughput in a router, switch or similar network device. The present invention provides a novel solution to this need.